//package indigo6a.train.algorithm.graph;
//
//import java.util.Arrays;
//import java.util.Stack;
//
//public class AoeMain {
//    static int[] etv;
//    static int[] ltv;
//    static Stack<Integer> topologicPath;
//    public static void main(String[] args) {
//        int numVertexes = 10;
//        // 初始化数据
//        VNode[] vertexes = new VNode[numVertexes];
//        vertexes[0] = new VNode(createArcNodeList(new int[][]{{2,4},{1,3}}),0);
//        vertexes[1] = new VNode(createArcNodeList(new int[][]{{4,6},{3,5}}),1);
//        vertexes[2] = new VNode(createArcNodeList(new int[][]{{5,7},{3,8}}),1);
//        vertexes[3] = new VNode(createArcNodeList(new int[][]{{4,3}}),2);
//        vertexes[4] = new VNode(createArcNodeList(new int[][]{{7,4},{6,9}}),2);
//        vertexes[5] = new VNode(createArcNodeList(new int[][]{{7,6}}),1);
//        vertexes[6] = new VNode(createArcNodeList(new int[][]{{9,2}}),1);
//        vertexes[7] = new VNode(createArcNodeList(new int[][]{{8,5}}),2);
//        vertexes[8] = new VNode(createArcNodeList(new int[][]{{9,3}}),1);
//        vertexes[9] = new VNode(null,2);
//
//        System.out.println(Arrays.toString(vertexes));
//
//        GraphAdjList graph = new GraphAdjList(numVertexes,vertexes);
//        TopologicalSort(graph);
//    }
//    public static void TopologicalSort(GraphAdjList graph) {
//        // 路径
//        topologicPath = new Stack<>();
//        // 最早发生时间
//        etv = new int[graph.getNumVertexes()];
//        // 最晚发生时间
//        ltv = new int[graph.getNumVertexes()];
//        Stack<Integer> processingVer = new Stack<>();
//        for(int i=0;i<graph.getNumVertexes();i++) {
//            if(graph.getVertexes()[i].getIn()==0) {
//                processingVer.push(i);
//            }
//        }
//        while(!processingVer.empty()) {
//            int aim = processingVer.pop();
//            path.push(aim);
//            System.out.println("process："+aim);
//            // 处理各边
//            for(ArcNode node= graph.getVertexes()[aim].getFirstArc();node!=null;node=node.getNextArc()) {
//                int nowNodeAdj = node.getAdjVex();
//                // 更新到达nowNodeAdj的最长距离
//                if(etv[aim]+node.getWeight()>etv[nowNodeAdj]) {
//                    etv[nowNodeAdj]=etv[aim]+node.getWeight();
//                }
//                // 入度-1,如果0了就开始处理
//                graph.getVertexes()[node.getAdjVex()].setIn(graph.getVertexes()[node.getAdjVex()].getIn()-1);
//                if(graph.getVertexes()[node.getAdjVex()].getIn()==0) {
//                    processingVer.push(node.getAdjVex());
//                }
//            }
//        }
//
//        System.out.println(Arrays.toString(etv));
//    }
//    // 求关键路径
//    public static void CriticalPath(GraphAdjList graph) {
//        lte = new int[graph.getNumVertexes()];
//        // 计算lte
//        Arrays.fill(lte,etv[graph.getNumVertexes()-1]);
//        while(!topologicPath.isEmpty()) {
//            Integer pop = topologicPath.pop();
//            if(pop!= graph.getNumVertexes()-1) {
//                for(ArcNode node= graph.getVertexes()[pop].getFirstArc();node!=null;node=node.getNextArc()) {
//                    int nowNodeAdj = node.getAdjVex();
//                    // 更新到达nowNodeAdj的最长距离
//                    if(ltv[nowNodeAdj]+node.getWeight()<ltv[nowNodeAdj]) {
//                        etv[nowNodeAdj]=etv[aim]+node.getWeight();
//                    }
//                    // 入度-1,如果0了就开始处理
//                    graph.getVertexes()[node.getAdjVex()].setIn(graph.getVertexes()[node.getAdjVex()].getIn()-1);
//                    if(graph.getVertexes()[node.getAdjVex()].getIn()==0) {
//                        processingVer.push(node.getAdjVex());
//                    }
//                }
//            }
//        }
//
//    }
//    public static ArcNode createArcNodeList(int[][]data) {
//        ArcNode first = new ArcNode(data[0][0],data[0][1]);
//        ArcNode parent = first;
//        for(int i=1;i<data.length;i++)
//        {
//            ArcNode temp = new ArcNode(data[i][0],data[i][1]);
//            parent.setNextArc(temp);
//            parent = temp;
//        }
//        return first;
//    }
//
//}
